
#include "tree_structures.h"
#include <limits.h>
#include <string.h>
#include <math.h>

using namespace std;

//Used by searchRecord() to return the record associated with the search key.  Returns NULL if record not found;
Record * LeafNode::returnRecordInLeaf(int searchKey) {
	for(int x=0; x < q; x++) {
		if(keys[x] == searchKey) {
			return records[x];
		}
	}
	return NULL;
}

//splits the leaf node and returns an IndexNode containing the key and pointer to be inserted in the above index node
IndexNode * LeafNode::splitLeafNode(int rightNodeHighKey) {
	int divIndex = ceil((d+1)/2) - 1;

	q = divIndex+1;
	LeafNode *rightLeafNode = new LeafNode(d);
	rightLeafNode->q = d-divIndex;

	IndexNode* newRoot = new IndexNode(d);
	newRoot->q = 1;
	newRoot->keys[0] = keys[divIndex];
	newRoot->nodePtrs[0] = this;
	newRoot->nodePtrs[1] = rightLeafNode;

	memcpy(rightLeafNode->keys, &keys[divIndex+1], 4*(d-divIndex));
	memcpy(rightLeafNode->records, &records[divIndex+1], 4*(d-divIndex));

	rightLeafNode->nextLeaf = nextLeaf;
	nextLeaf = rightLeafNode;

	highKey = keys[divIndex];
	rightLeafNode->highKey = rightNodeHighKey;

	return newRoot;
}

//inserts the record in the leaf: returns 1 if successful, returns 0 if record already in leaf
int LeafNode::insertRecordInLeaf(int key, Record* record) {

	if(q == 0) {	//empty leaf case
		keys[0] = key;
		records[0] = record;
		q++;
		return 1;
	}
	else {
		if(key > keys[q-1]) { //inserted record has the highest key
			records[q] = record;
			keys[q] = key;
			q++;
			return 1;
		}
		else { 			//record is inserted somewhere in the middle of the node
			for(int index=0; index < q; index++) {
				if(key == keys[index])
					return 0;
				else if(key < keys[index]) {
					//Save next entry into temp
					Record* recordTemp = records[index];
					int keyTemp = keys[index];

					Record* recordTemp2;
					int keyTemp2;

					//Set current index to new record
					records[index] = record;
					keys[index] = key;

					for(int x=index+1; x < (q + 1); x++) {
						recordTemp2 = records[x];
						keyTemp2 = keys[x];

						records[x] = recordTemp;
						keys[x] = keyTemp;

						recordTemp = recordTemp2;
						keyTemp = keyTemp2;
					}
					q++;
					break;
				}
			}
			return 1;
		}
	}
}


//Helper Function for printIndex() to print all keys in a node
void Node::printKeysNode() {
	for(int x=0; x<q; x++) {
		if(x != q-1)
			cout << keys[x] << ", ";
		else
			cout << keys[x];
	}
		cout << ": " << highKey << "\t\t";
}

//inserts a key in an index node from a split node below
void IndexNode::insertKeyInIndex(IndexNode* temp, int index) {

	if(index == q) {
		keys[index] = temp->keys[0];
		nodePtrs[index] = temp->nodePtrs[0];
		nodePtrs[index+1] = temp->nodePtrs[1];
		q++;
	}
	else {
		Node *lastPtr = nodePtrs[q];

		Node* nodePtrTemp = temp->nodePtrs[1];
		int keyTemp = keys[index];

		Node* nodePtrTemp2;
		int keyTemp2;

		keys[index] = temp->keys[0];
		nodePtrs[index] = temp->nodePtrs[0];

		for(int x=index+1; x < (q + 1); x++) {
			nodePtrTemp2 = nodePtrs[x];
			keyTemp2 = keys[x];

			nodePtrs[x] = nodePtrTemp;
			keys[x] = keyTemp;

			nodePtrTemp = nodePtrTemp2;
			keyTemp = keyTemp2;
		}
		q++;
		nodePtrs[q] = lastPtr;
	}
}

//splits the current index node and returns an IndexNode containing the key and pointer to be inserted in the above index node
IndexNode * IndexNode::splitIndexNode(int rightNodeHighKey) {
	int divIndex = ceil((d+1)/2) - 1;

	q = divIndex;
	IndexNode *rightIndexNode = new IndexNode(d);
	rightIndexNode->q = d-divIndex;

	IndexNode* newRoot = new IndexNode(d);
	newRoot->q = 1;
	newRoot->keys[0] = keys[divIndex];
	newRoot->nodePtrs[0] = this;
	newRoot->nodePtrs[1] = rightIndexNode;

	memcpy(rightIndexNode->keys, &keys[divIndex+1], 4*(d-divIndex));
	memcpy(rightIndexNode->nodePtrs, &nodePtrs[divIndex+1], 4*(d-divIndex+1));

	rightIndexNode->nextNode = nextNode;
	nextNode = rightIndexNode;

	highKey = keys[divIndex];
	rightIndexNode->highKey = rightNodeHighKey;

	return newRoot;
}


//helper function to determine if the current node is full
bool Node::isNodeFull() {
	return q==d;
}
